package graph.day15;

import java.util.ArrayList;
import java.util.List;

public class Leetcode_1382 {

    List<Integer> inorderSeq = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        inorder(root);
        return build(0, inorderSeq.size() - 1);
    }

    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        inorderSeq.add(root.val);
        inorder(root.right);
    }

    public TreeNode build(int l, int r) {
        if (l > r) return null;
        int mid = (l + r) >> 1;
        TreeNode midNode = new TreeNode(inorderSeq.get(mid));
        midNode.left = build(l, mid - 1);
        midNode.right = build(mid + 1, r);
        return midNode;
    }

}
